home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 7 / Apprentice-Release7.iso / Environments / PowerLisp 2.01 / Supplemental Documentation / Documentation / Chapter 14. Sequences < prev    next >
Text File  |  1995-03-27  |  52KB  |  1,190 lines
  1. Common Lisp the Language, 2nd Edition
  2. -------------------------------------------------------------------------------
  3.  
  4. 14. Sequences
  5.  
  6. The type sequence encompasses both lists and vectors (one-dimensional arrays).
  7. While these are different data structures with different structural properties
  8. leading to different algorithmic uses, they do have a common property: each
  9. contains an ordered set of elements. Note that nil is considered to be a
  10. sequence of length zero.
  11.  
  12. Some operations are useful on both lists and arrays because they deal with
  13. ordered sets of elements. One may ask the number of elements, reverse the
  14. ordering, extract a subsequence, and so on. For such purposes Common Lisp
  15. provides a set of generic functions on sequences.
  16.  
  17. [change_begin]
  18. Note that this remark, predating the design of the Common Lisp Object System,
  19. uses the term ``generic'' in a generic sense, and not necessarily in the
  20. technical sense used by CLOS (see chapter 2).
  21. [change_end]
  22.  
  23. elt          reverse        map           remove
  24. length       nreverse       some          remove-duplicates
  25. subseq       concatenate    every         delete
  26. copy-seq     position       notany        delete-duplicates
  27. fill         find           notevery      substitute
  28. replace      sort           reduce        nsubstitute
  29. count        merge          search        mismatch
  30.  
  31. Some of these operations come in more than one version. Such versions are
  32. indicated by adding a suffix (or occasionally a prefix) to the basic name of
  33. the operation. In addition, many operations accept one or more optional keyword
  34. arguments that can modify the operation in various ways.
  35.  
  36. If the operation requires testing sequence elements according to some
  37. criterion, then the criterion may be specified in one of two ways. The basic
  38. operation accepts an item, and elements are tested for being eql to that item.
  39. (A test other than eql can be specified by the :test or :test-not keyword. It
  40. is an error to use both of these keywords in the same call.) The variants
  41. formed by adding -if and -if-not to the basic operation name do not take an
  42. item, but instead a one-argument predicate, and elements are tested for
  43. satisfying or not satisfying the predicate. As an example,
  44.  
  45. (remove item sequence)
  46.  
  47. returns a copy of sequence from which all elements eql to item have been
  48. removed;
  49.  
  50. (remove item sequence :test #'equal)
  51.  
  52. returns a copy of sequence from which all elements equal to item have been
  53. removed;
  54.  
  55. (remove-if #'numberp sequence)
  56.  
  57. returns a copy of sequence from which all numbers have been removed.
  58.  
  59. If an operation tests elements of a sequence in any manner, the keyword
  60. argument :key, if not nil, should be a function of one argument that will
  61. extract from an element the part to be tested in place of the whole element.
  62. For example, the effect of the MacLisp expression (assq item seq) could be
  63. obtained by
  64.  
  65. (find item sequence :test #'eq :key #'car)
  66.  
  67. This searches for the first element of sequence whose car is eq to item.
  68.  
  69. [change_begin]
  70. X3J13 voted in June 1988 (FUNCTION-TYPE)   to allow the :key function to be
  71. only of type symbol or function; a lambda-expression is no longer acceptable as
  72. a functional argument. One must use the function special form or the
  73. abbreviation #' before a lambda-expression that appears as an explicit argument
  74. form.
  75. [change_end]
  76.  
  77. For some operations it can be useful to specify the direction in which the
  78. sequence is conceptually processed. In this case the basic operation normally
  79. processes the sequence in the forward direction, and processing in the reverse
  80. direction is indicated by a non-nil value for the keyword argument :from-end.
  81. (The processing order specified by the :from-end is purely conceptual.
  82. Depending on the object to be processed and on the implementation, the actual
  83. processing order may be different. For this reason a user-supplied test
  84. function should be free of side effects.)
  85.  
  86. Many operations allow the specification of a subsequence to be operated upon.
  87. Such operations have keyword arguments called :start and :end. These arguments
  88. should be integer indices into the sequence, with startend (it is an error if
  89. start>end). They indicate the subsequence starting with and including element
  90. start and up to but excluding element end. The length of the subsequence is
  91. therefore end-start. If start is omitted, it defaults to zero; and if end is
  92. omitted or nil, it defaults to the length of the sequence. Therefore if both
  93. start and end are omitted, the entire sequence is processed by default. For the
  94. most part, subsequence specification is permitted purely for the sake of
  95. efficiency; one could simply call subseq instead to extract the subsequence
  96. before operating on it. Note, however, that operations that calculate indices
  97. return indices into the original sequence, not into the subsequence:
  98.  
  99. (position #\b "foobar" :start 2 :end 5) => 3
  100. (position #\b (subseq "foobar" 2 5)) => 1
  101.  
  102. If two sequences are involved, then the keyword arguments :start1, :end1,
  103. :start2, and :end2 are used to specify separate subsequences for each sequence.
  104.  
  105. [change_begin]
  106. X3J13 voted in June 1988 (SUBSEQ-OUT-OF-BOUNDS)   (and further clarification
  107. was voted in January 1989 (RANGE-OF-START-AND-END-PARAMETERS)   ) to specify
  108. that these rules apply not only to all built-in functions that have keyword
  109. parameters named :start, :start1, :start2, :end, :end1, or :end2 but also to
  110. functions such as subseq that take required or optional parameters that are
  111. documented as being named start or end.
  112.  
  113.    *  A ``start'' argument must always be a non-negative integer and defaults
  114.      to zero if not supplied; it is not permissible to pass nil as a ``start''
  115.      argument.
  116.  
  117.    *  An ``end'' argument must be either a non-negative integer or nil (which
  118.      indicates the end of the sequence) and defaults to nil if not supplied;
  119.      therefore supplying nil is equivalent to not supplying such an argument.
  120.  
  121.    *  If the ``end'' argument is an integer, it must be no greater than the
  122.      active length of the corresponding sequence (as returned by the function
  123.      length).
  124.  
  125.    *  The default value for the ``end'' argument is the active length of the
  126.      corresponding sequence.
  127.  
  128.    *  The ``start'' value (after defaulting, if necessary) must not be greater
  129.      than the corresponding ``end'' value (after defaulting, if necessary).
  130.  
  131. This may be summarized as follows. Let x be the sequence within which indices
  132. are to be considered. Let s be the ``start'' argument for that sequence of any
  133. standard function, whether explicitly specified or defaulted, through omission,
  134. to zero. Let e be the ``end'' argument for that sequence of any standard
  135. function, whether explicitly specified or defaulted, through omission or an
  136. explicitly passed nil value, to the active length of x, as returned by length.
  137. Then it is an error if the test (<= 0 s e (length x)) is not true.
  138. [change_end]
  139.  
  140. For some functions, notably remove and delete, the keyword argument :count is
  141. used to specify how many occurrences of the item should be affected. If this is
  142. nil or is not supplied, all matching items are affected.
  143.  
  144. In the following function descriptions, an element x of a sequence ``satisfies
  145. the test'' if any of the following holds:
  146.  
  147.    *  A basic function was called, testfn was specified by the keyword :test,
  148.      and (funcall testfn item (keyfn x)) is true.
  149.  
  150.    *  A basic function was called, testfn was specified by the keyword
  151.      :test-not, and (funcall testfn item (keyfn x)) is false.
  152.  
  153.    *  An -if function was called, and (funcall predicate (keyfn x)) is true.
  154.  
  155.    *  An -if-not function was called, and (funcall predicate (keyfn x)) is
  156.      false.
  157.  
  158. In each case keyfn is the value of the :key keyword argument (the default being
  159. the identity function). See, for example, remove.
  160.  
  161. In the following function descriptions, two elements x and y taken from
  162. sequences ``match'' if either of the following holds:
  163.  
  164.    *  testfn was specified by the keyword :test, and (funcall testfn (keyfn x)
  165.      (keyfn y)) is true.
  166.  
  167.    *  testfn was specified by the keyword :test-not, and (funcall testfn (keyfn
  168.      x) (keyfn y)) is false.
  169.  
  170. See, for example, search.
  171.  
  172. [change_begin]
  173. X3J13 voted in June 1988 (FUNCTION-TYPE)   to allow the testfn or predicate to
  174. be only of type symbol or function; a lambda-expression is no longer acceptable
  175. as a functional argument. One must use the function special form or the
  176. abbreviation #' before a lambda-expression that appears as an explicit argument
  177. form.
  178. [change_end]
  179.  
  180. You may depend on the order in which arguments are given to testfn; this
  181. permits the use of non-commutative test functions in a predictable manner. The
  182. order of the arguments to testfn corresponds to the order in which those
  183. arguments (or the sequences containing those arguments) were given to the
  184. sequence function in question. If a sequence function gives two elements from
  185. the same sequence argument to testfn, they are given in the same order in which
  186. they appear in the sequence.
  187.  
  188. Whenever a sequence function must construct and return a new vector, it always
  189. returns a simple vector (see section 2.5). Similarly, any strings constructed
  190. will be simple strings.
  191.  
  192. [change_begin]
  193. X3J13 voted in January 1989 (TEST-NOT-IF-NOT)   to deprecate the use of
  194. :test-not keyword arguments and -if-not functions. This means that these
  195. features are very likely to be retained in the forthcoming standard but are
  196. regarded as candidates for removal in a future revision of the ANSI standard.
  197. X3J13 also voted in January 1989 (FUNCTION-COMPOSITION)   to add the complement
  198. function, intended to reduce or eliminate the need for these deprecated
  199. features. Time will tell. I note that many features in Fortran have been
  200. deprecated but very few indeed have actually been removed or altered
  201. incompatibly.
  202.  
  203. [Function]
  204. complement fn
  205.  
  206. Returns a function whose value is the same as that of not applied to the result
  207. of applying the function fn to the same arguments. One could define complement
  208. as follows:
  209.  
  210. (defun complement (fn)
  211.   #'(lambda (&rest arguments)
  212.       (not (apply fn arguments))))
  213.  
  214. One intended use of complement is to supplant the use of :test-not arguments
  215. and -if-not functions.
  216.  
  217. (remove-if-not #'virtuous senators) ==
  218.    (remove-if (complement #'virtuous) senators)
  219.  
  220. (remove-duplicates telephone-book
  221.                    :test-not #'mismatch) ==
  222.    (remove-duplicates telephone-book
  223.                       :test (complement #'mismatch))
  224.  
  225. [change_end]
  226.  
  227. -------------------------------------------------------------------------------
  228.  
  229.    *  Simple Sequence Functions
  230.    *  Concatenating, Mapping, and Reducing Sequences
  231.    *  Modifying Sequences
  232.    *  Searching Sequences for Items
  233.    *  Sorting and Merging
  234.  
  235. -------------------------------------------------------------------------------
  236.  
  237. 14.1. Simple Sequence Functions
  238.  
  239. Most of the following functions perform simple operations on a single sequence;
  240. make-sequence constructs a new sequence.
  241.  
  242. [Function]
  243. elt sequence index
  244.  
  245. This returns the element of sequence specified by index, which must be a
  246. non-negative integer less than the length of the sequence as returned by
  247. length. The first element of a sequence has index 0.
  248.  
  249. (Note that elt observes the fill pointer in those vectors that have fill
  250. pointers. The array-specific function aref may be used to access vector
  251. elements that are beyond the vector's fill pointer.)
  252.  
  253. setf may be used with elt to destructively replace a sequence element with a
  254. new value.
  255.  
  256. [Function]
  257. subseq sequence start &optional end
  258.  
  259. This returns the subsequence of sequence specified by start and end. subseq
  260. always allocates a new sequence for a result; it never shares storage with an
  261. old sequence. The result subsequence is always of the same type as the argument
  262. sequence.
  263.  
  264. setf may be used with subseq to destructively replace a subsequence with a
  265. sequence of new values; see also replace.
  266.  
  267. [Function]
  268. copy-seq sequence
  269.  
  270. A copy is made of the argument sequence; the result is equalp to the argument
  271. but not eq to it.
  272.  
  273. (copy-seq x) == (subseq x 0)
  274.  
  275. but the name copy-seq is more perspicuous when applicable.
  276.  
  277. [Function]
  278. length sequence
  279.  
  280. The number of elements in sequence is returned as a non-negative integer. If
  281. the sequence is a vector with a fill pointer, the ``active length'' as
  282. specified by the fill pointer is returned (see section 17.5).
  283.  
  284. [Function]
  285. reverse sequence
  286.  
  287. The result is a new sequence of the same kind as sequence, containing the same
  288. elements but in reverse order. The argument is not modified.
  289.  
  290. [Function]
  291. nreverse sequence
  292.  
  293. The result is a sequence containing the same elements as sequence but in
  294. reverse order. The argument may be destroyed and re-used to produce the result.
  295. The result may or may not be eq to the argument, so it is usually wise to say
  296. something like (setq x (nreverse x)), because simply (nreverse x) is not
  297. guaranteed to leave a reversed value in x.
  298.  
  299. [change_begin]
  300. X3J13 voted in March 1989 (REMF-DESTRUCTION-UNSPECIFIED)   to clarify the
  301. permissible side effects of certain operations. When the sequence is a list,
  302. nreverse is permitted to perform a setf on any part, car or cdr, of the
  303. top-level list structure of that list. When the sequence is an array, nreverse
  304. is permitted to re-order the elements of the given array in order to produce
  305. the resulting array.
  306. [change_end]
  307.  
  308. [Function]
  309. make-sequence type size &key :initial-element
  310.  
  311. This returns a sequence of type type and of length size, each of whose elements
  312. has been initialized to the :initial-element argument. If specified, the
  313. :initial-element argument must be an object that can be an element of a
  314. sequence of type type. For example:
  315.  
  316. (make-sequence '(vector double-float)
  317.                100
  318.                :initial-element 1d0)
  319.  
  320. If an :initial-element argument is not specified, then the sequence will be
  321. initialized in an implementation-dependent way.
  322.  
  323. [change_begin]
  324. X3J13 voted in January 1989 (ARGUMENTS-UNDERSPECIFIED)   to clarify that the
  325. type argument must be a type specifier, and the size argument must be a
  326. non-negative integer less than the value of array-dimension-limit.
  327.  
  328. X3J13 voted in June 1989 (SEQUENCE-TYPE-LENGTH)   to specify that make-sequence
  329. should signal an error if the sequence type specifies the number of elements
  330. and the size argument is different.
  331.  
  332. X3J13 voted in March 1989 (CHARACTER-PROPOSAL)   to specify that if type is
  333. string, the result is the same as if make-string had been called with the same
  334. size and :initial-element arguments.
  335. [change_end]
  336.  
  337. -------------------------------------------------------------------------------
  338.  
  339. 14.2. Concatenating, Mapping, and Reducing Sequences
  340.  
  341. The functions in this section each operate on an arbitrary number of sequences
  342. except for reduce, which is included here because of its conceptual
  343. relationship to the mapping functions.
  344.  
  345. [Function]
  346. concatenate result-type &rest sequences
  347.  
  348. The result is a new sequence that contains all the elements of all the
  349. sequences in order. All of the sequences are copied from; the result does not
  350. share any structure with any of the argument sequences (in this concatenate
  351. differs from append). The type of the result is specified by result-type, which
  352. must be a subtype of sequence, as for the function coerce. It must be possible
  353. for every element of the argument sequences to be an element of a sequence of
  354. type result-type.
  355.  
  356. If only one sequence argument is provided and it has the type specified by
  357. result-type, concatenate is required to copy the argument rather than simply
  358. returning it. If a copy is not required, but only possibly type conversion,
  359. then the coerce function may be appropriate.
  360.  
  361. [change_begin]
  362. X3J13 voted in June 1989 (SEQUENCE-TYPE-LENGTH)   to specify that concatenate
  363. should signal an error if the sequence type specifies the number of elements
  364. and the sum of the argument lengths is different.
  365. [change_end]
  366.  
  367. [Function]
  368. map result-type function sequence &rest more-sequences
  369.  
  370. The function must take as many arguments as there are sequences provided; at
  371. least one sequence must be provided. The result of map is a sequence such that
  372. element j is the result of applying function to element j of each of the
  373. argument sequences. The result sequence is as long as the shortest of the input
  374. sequences.
  375.  
  376. If the function has side effects, it can count on being called first on all the
  377. elements numbered 0, then on all those numbered 1, and so on.
  378.  
  379. The type of the result sequence is specified by the argument result-type (which
  380. must be a subtype of the type sequence), as for the function coerce. In
  381. addition, one may specify nil for the result type, meaning that no result
  382. sequence is to be produced; in this case the function is invoked only for
  383. effect, and map returns nil. This gives an effect similar to that of mapc.
  384.  
  385. [change_begin]
  386. X3J13 voted in June 1989 (SEQUENCE-TYPE-LENGTH)   to specify that map should
  387. signal an error if the sequence type specifies the number of elements and the
  388. minimum of the argument lengths is different.
  389.  
  390. X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION)   to restrict
  391. user side effects; see section 7.9.
  392. [change_end]
  393.  
  394. -------------------------------------------------------------------------------
  395. Compatibility note: In MacLisp, Lisp Machine Lisp, Interlisp, and indeed even
  396. Lisp 1.5, the function map has always meant a non-value-returning version.
  397. However, standard computer science literature, including in particular the
  398. recent wave of papers on ``functional programming,'' have come to use map to
  399. mean what in the past Lisp implementations have called mapcar. To simplify
  400. things henceforth, Common Lisp follows current usage, and what was formerly
  401. called map is named mapl in Common Lisp.
  402. -------------------------------------------------------------------------------
  403.  
  404. For example:
  405.  
  406. (map 'list #'- '(1 2 3 4)) => (-1 -2 -3 -4)
  407. (map 'string
  408.      #'(lambda (x) (if (oddp x) #\1 #\0))
  409.      '(1 2 3 4))
  410.    => "1010"
  411.  
  412. [change_begin]
  413.  
  414. [Function]
  415. map-into result-sequence function &rest sequences
  416.  
  417. X3J13 voted in June 1989 (MAP-INTO)   to add the function map-into. It
  418. destructively modifies the result-sequence to contain the results of applying
  419. function to corresponding elements of the argument sequences in turn; it then
  420. returns result-sequence.
  421.  
  422. The arguments result-sequence and each element of sequences can each be either
  423. a list or a vector (one-dimensional array). The function must accept at least
  424. as many arguments as the number of argument sequences supplied to map-into. If
  425. result-sequence and the other argument sequences are not all the same length,
  426. the iteration terminates when the shortest sequence is exhausted. If
  427. result-sequence is a vector with a fill pointer, the fill pointer is ignored
  428. when deciding how many iterations to perform, and afterwards the fill pointer
  429. is set to the number of times the function was applied.
  430.  
  431. If the function has side effects, it can count on being called first on all the
  432. elements numbered 0, then on all those numbered 1, and so on.
  433.  
  434. If result-sequence is longer than the shortest element of sequences, extra
  435. elements at the end of result-sequence are unchanged.
  436.  
  437. The function map-into differs from map in that it modifies an existing sequence
  438. rather than creating a new one. In addition, map-into can be called with only
  439. two arguments (result-sequence and function), while map requires at least three
  440. arguments.
  441.  
  442. If result-sequence is nil, map-into immediately returns nil, because nil is a
  443. sequence of length zero.
  444. [change_end]
  445.  
  446. [Function]
  447. some predicate sequence &rest more-sequences
  448. every predicate sequence &rest more-sequences
  449. notany predicate sequence &rest more-sequences
  450. notevery predicate sequence &rest more-sequences
  451.  
  452. These are all predicates. The predicate must take as many arguments as there
  453. are sequences provided. The predicate is first applied to the elements with
  454. index 0 in each of the sequences, and possibly then to the elements with index
  455. 1, and so on, until a termination criterion is met or the end of the shortest
  456. of the sequences is reached.
  457.  
  458. If the predicate has side effects, it can count on being called first on all
  459. the elements numbered 0, then on all those numbered 1, and so on.
  460.  
  461. some returns as soon as any invocation of predicate returns a non-nil value;
  462. some returns that value. If the end of a sequence is reached, some returns nil.
  463. Thus, considered as a predicate, it is true if some invocation of predicate is
  464. true.
  465.  
  466. every returns nil as soon as any invocation of predicate returns nil. If the
  467. end of a sequence is reached, every returns a non-nil value. Thus, considered
  468. as a predicate, it is true if every invocation of predicate is true.
  469.  
  470. notany returns nil as soon as any invocation of predicate returns a non-nil
  471. value. If the end of a sequence is reached, notany returns a non-nil value.
  472. Thus, considered as a predicate, it is true if no invocation of predicate is
  473. true.
  474.  
  475. notevery returns a non-nil value as soon as any invocation of predicate returns
  476. nil. If the end of a sequence is reached, notevery returns nil. Thus,
  477. considered as a predicate, it is true if not every invocation of predicate is
  478. true.
  479.  
  480. [change_begin]
  481. X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION)   to restrict
  482. user side effects; see section 7.9.
  483. [change_end]
  484.  
  485. -------------------------------------------------------------------------------
  486. Compatibility note: The order of the arguments here is not compatible with
  487. Interlisp and Lisp Machine Lisp. This is to stress the similarity of these
  488. functions to map. The functions are therefore extended here to functions of
  489. more than one argument, and to multiple sequences.
  490. -------------------------------------------------------------------------------
  491.  
  492. [Function]
  493. reduce function sequence &key :from-end :start :end :initial-value
  494.  
  495. The reduce function combines all the elements of a sequence using a binary
  496. operation; for example, using + one can add up all the elements.
  497.  
  498. The specified subsequence of the sequence is combined or ``reduced'' using the
  499. function, which must accept two arguments. The reduction is left-associative,
  500. unless the :from-end argument is true (it defaults to nil), in which case it is
  501. right-associative. If an :initial-value argument is given, it is logically
  502. placed before the subsequence (after it if :from-end is true) and included in
  503. the reduction operation.
  504.  
  505. If the specified subsequence contains exactly one element and the keyword
  506. argument :initial-value is not given, then that element is returned and the
  507. function is not called. If the specified subsequence is empty and an
  508. :initial-value is given, then the :initial-value is returned and the function
  509. is not called.
  510.  
  511. If the specified subsequence is empty and no :initial-value is given, then the
  512. function is called with zero arguments, and reduce returns whatever the
  513. function does. (This is the only case where the function is called with other
  514. than two arguments.)
  515.  
  516. (reduce #'+ '(1 2 3 4)) => 10
  517. (reduce #'- '(1 2 3 4)) == (- (- (- 1 2) 3) 4) => -8
  518. (reduce #'- '(1 2 3 4) :from-end t)     ;Alternating sum
  519.    == (- 1 (- 2 (- 3 4))) => -2
  520. (reduce #'+ '()) => 0
  521. (reduce #'+ '(3)) => 3
  522. (reduce #'+ '(foo)) => foo
  523. (reduce #'list '(1 2 3 4)) => (((1 2) 3) 4)
  524. (reduce #'list '(1 2 3 4) :from-end t) => (1 (2 (3 4)))
  525. (reduce #'list '(1 2 3 4) :initial-value 'foo)
  526.    => ((((foo 1) 2) 3) 4)
  527. (reduce #'list '(1 2 3 4)
  528.         :from-end t :initial-value 'foo)
  529.    => (1 (2 (3 (4 foo))))
  530.  
  531. If the function produces side effects, the order of the calls to the function
  532. can be correctly predicted from the reduction ordering demonstrated above.
  533.  
  534. [change_begin]
  535. The name ``reduce'' for this function is borrowed from APL.
  536.  
  537. X3J13 voted in March 1988 (REDUCE-ARGUMENT-EXTRACTION)   to extend the reduce
  538. function to take an additional keyword argument named :key. As usual, this
  539. argument defaults to the identity function. The value of this argument must be
  540. a function that accepts at least one argument. This function is applied once to
  541. each element of the sequence that is to participate in the reduction operation,
  542. in the order implied by the :from-end argument; the values returned by this
  543. function are combined by the reduction function. However, the :key function is
  544. not applied to the :initial-value argument (if any).
  545.  
  546. X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION)   to restrict
  547. user side effects; see section 7.9.
  548. [change_end]
  549.  
  550. -------------------------------------------------------------------------------
  551.  
  552. 14.3. Modifying Sequences
  553.  
  554. Each of these functions alters the contents of a sequence or produces an
  555. altered copy of a given sequence.
  556.  
  557. [Function]
  558. fill sequence item &key :start :end
  559.  
  560. The sequence is destructively modified by replacing each element of the
  561. subsequence specified by the :start and :end parameters with the item. The item
  562. may be any Lisp object but must be a suitable element for the sequence. The
  563. item is stored into all specified components of the sequence, beginning at the
  564. one specified by the :start index (which defaults to zero), up to but not
  565. including the one specified by the :end index (which defaults to the length of
  566. the sequence). fill returns the modified sequence. For example:
  567.  
  568. (setq x (vector 'a 'b 'c 'd 'e)) => #(a b c d e)
  569. (fill x 'z :start 1 :end 3) => #(a z z d e)
  570.   and now x => #(a z z d e)
  571. (fill x 'p) => #(p p p p p)
  572.   and now x => #(p p p p p)
  573.  
  574. [Function]
  575. replace sequence1 sequence2 &key :start1 :end1 :start2 :end2
  576.  
  577. The sequence sequence1 is destructively modified by copying successive elements
  578. into it from sequence2. The elements of sequence2 must be of a type that may be
  579. stored into sequence1. The subsequence of sequence2 specified by :start2 and
  580. :end2 is copied into the subsequence of sequence1 specified by :start1 and
  581. :end1. (The arguments :start1 and :start2 default to zero. The arguments :end1
  582. and :end2 default to nil, meaning the end of the appropriate sequence.) If
  583. these subsequences are not of the same length, then the shorter length
  584. determines how many elements are copied; the extra elements near the end of the
  585. longer subsequence are not involved in the operation. The number of elements
  586. copied may be expressed as:
  587.  
  588. (min (- end1 start1) (- end2 start2))
  589.  
  590. The value returned by replace is the modified sequence1.
  591.  
  592. If sequence1 and sequence2 are the same (eq) object and the region being
  593. modified overlaps the region being copied from, then it is as if the entire
  594. source region were copied to another place and only then copied back into the
  595. target region. However, if sequence1 and sequence2 are not the same, but the
  596. region being modified overlaps the region being copied from (perhaps because of
  597. shared list structure or displaced arrays), then after the replace operation
  598. the subsequence of sequence1 being modified will have unpredictable contents.
  599.  
  600. [Function]
  601.  
  602. remove item sequence &key :from-end :test :test-not
  603.            :start :end :count :key
  604. remove-if predicate sequence &key :from-end
  605.            :start :end :count :key
  606. remove-if-not predicate sequence &key :from-end
  607.            :start :end :count :key
  608.  
  609. The result is a sequence of the same kind as the argument sequence that has the
  610. same elements except that those in the subsequence delimited by :start and :end
  611. and satisfying the test (see above) have been removed. This is a
  612. non-destructive operation; the result is a copy of the input sequence, save
  613. that some elements are not copied. Elements not removed occur in the same order
  614. in the result as they did in the argument.
  615.  
  616. The :count argument, if supplied, limits the number of elements removed; if
  617. more than :count elements satisfy the test, then of these elements only the
  618. leftmost are removed, as many as specified by :count.
  619.  
  620. [change_begin]
  621. X3J13 voted in January 1989 (RANGE-OF-COUNT-KEYWORD)   to clarify that the
  622. :count argument must be either nil or an integer, and that supplying a negative
  623. integer produces the same behavior as supplying zero.
  624. [change_end]
  625.  
  626. A non-nil :from-end specification matters only when the :count argument is
  627. provided; in that case only the rightmost :count elements satisfying the test
  628. are removed. For example:
  629.  
  630. (remove 4 '(1 2 4 1 3 4 5)) => (1 2 1 3 5)
  631. (remove 4 '(1 2 4 1 3 4 5) :count 1) => (1 2 1 3 4 5)
  632. (remove 4 '(1 2 4 1 3 4 5) :count 1 :from-end t)
  633.    => (1 2 4 1 3 5)
  634. (remove 3 '(1 2 4 1 3 4 5) :test #'>) => (4 3 4 5)
  635. (remove-if #'oddp '(1 2 4 1 3 4 5)) => (2 4 4)
  636. (remove-if #'evenp '(1 2 4 1 3 4 5) :count 1 :from-end t)
  637.    => (1 2 4 1 3 5)
  638.  
  639. The result of remove may share with the argument sequence; a list result may
  640. share a tail with an input list, and the result may be eq to the input sequence
  641. if no elements need to be removed.
  642.  
  643. [change_begin]
  644. X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION)   to restrict
  645. user side effects; see section 7.9.
  646. [change_end]
  647.  
  648. [Function]
  649.  
  650. delete item sequence &key :from-end :test :test-not
  651.            :start :end :count :key
  652. delete-if predicate sequence &key :from-end
  653.            :start :end :count :key
  654. delete-if-not predicate sequence &key :from-end
  655.            :start :end :count :key
  656.  
  657. This is the destructive counterpart to remove. The result is a sequence of the
  658. same kind as the argument sequence that has the same elements except that those
  659. in the subsequence delimited by :start and :end and satisfying the test (see
  660. above) have been deleted. This is a destructive operation. The argument
  661. sequence may be destroyed and used to construct the result; however, the result
  662. may or may not be eq to sequence. Elements not deleted occur in the same order
  663. in the result as they did in the argument.
  664.  
  665. The :count argument, if supplied, limits the number of elements deleted; if
  666. more than :count elements satisfy the test, then of these elements only the
  667. leftmost are deleted, as many as specified by :count.
  668.  
  669. [change_begin]
  670. X3J13 voted in January 1989 (RANGE-OF-COUNT-KEYWORD)   to clarify that the
  671. :count argument must be either nil or an integer, and that supplying a negative
  672. integer produces the same behavior as supplying zero.
  673. [change_end]
  674.  
  675. A non-nil :from-end specification matters only when the :count argument is
  676. provided; in that case only the rightmost :count elements satisfying the test
  677. are deleted. For example:
  678.  
  679. (delete 4 '(1 2 4 1 3 4 5)) => (1 2 1 3 5)
  680. (delete 4 '(1 2 4 1 3 4 5) :count 1) => (1 2 1 3 4 5)
  681. (delete 4 '(1 2 4 1 3 4 5) :count 1 :from-end t)
  682.    => (1 2 4 1 3 5)
  683. (delete 3 '(1 2 4 1 3 4 5) :test #'>) => (4 3 4 5)
  684. (delete-if #'oddp '(1 2 4 1 3 4 5)) => (2 4 4)
  685. (delete-if #'evenp '(1 2 4 1 3 4 5) :count 1 :from-end t)
  686.    => (1 2 4 1 3 5)
  687.  
  688. [change_begin]
  689. X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION)   to restrict
  690. user side effects; see section 7.9.
  691.  
  692. X3J13 voted in March 1989 (REMF-DESTRUCTION-UNSPECIFIED)   to clarify the
  693. permissible side effects of certain operations. When the sequence is a list,
  694. delete is permitted to perform a setf on any part, car or cdr, of the top-level
  695. list structure of that list. When the sequence is an array, delete is permitted
  696. to alter the dimensions of the given array and to slide some of its elements
  697. into new positions without permuting them in order to produce the resulting
  698. array.
  699.  
  700. Furthermore, (delete-if predicate sequence ...) is required to behave exactly
  701. like
  702.  
  703. (delete nil sequence
  704.         :test #'(lambda (unused item)
  705.                    (declare (ignore unused))
  706.                    (funcall predicate item))
  707.         ...)
  708.  
  709. [change_end]
  710.  
  711. -------------------------------------------------------------------------------
  712. Compatibility note: In MacLisp, the delete function uses an equal comparison
  713. rather than eql, which is the default test for delete in Common Lisp. Where in
  714. MacLisp one would write (delete x y), one must in Common Lisp write (delete x y
  715. :test #'equal) to get the completely identical effect. Similarly, one can get
  716. the precise effect, and no more, of the MacLisp (delq x y) by writing in Common
  717. Lisp (delete x y :test #'eq).
  718. -------------------------------------------------------------------------------
  719.  
  720. [Function]
  721.  
  722. remove-duplicates sequence &key :from-end :test :test-not
  723.               :start :end :key
  724. delete-duplicates sequence &key :from-end :test :test-not
  725.               :start :end :key
  726.  
  727. The elements of sequence are compared pairwise, and if any two match, then the
  728. one occurring earlier in the sequence is discarded (but if the :from-end
  729. argument is true, then the one later in the sequence is discarded). The result
  730. is a sequence of the same kind as the argument sequence with enough elements
  731. removed so that no two of the remaining elements match. The order of the
  732. elements remaining in the result is the same as the order in which they appear
  733. in sequence.
  734.  
  735. remove-duplicates is the non-destructive version of this operation. The result
  736. of remove-duplicates may share with the argument sequence; a list result may
  737. share a tail with an input list, and the result may be eq to the input sequence
  738. if no elements need to be removed.
  739.  
  740. delete-duplicates may destroy the argument sequence.
  741.  
  742. Some examples:
  743.  
  744. (remove-duplicates '(a b c b d d e)) => (a c b d e)
  745. (remove-duplicates '(a b c b d d e) :from-end t) => (a b c d e)
  746. (remove-duplicates '((foo #\a) (bar #\%) (baz #\A))
  747.                    :test #'char-equal :key #'cadr)
  748.    => ((bar #\%) (baz #\A))
  749. (remove-duplicates '((foo #\a) (bar #\%) (baz #\A))
  750.                    :test #'char-equal :key #'cadr :from-end t)
  751.    => ((foo #\a) (bar #\%))
  752.  
  753. These functions are useful for converting a sequence into a canonical form
  754. suitable for representing a set.
  755.  
  756. [change_begin]
  757. X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION)   to restrict
  758. user side effects; see section 7.9.
  759.  
  760. X3J13 voted in March 1989 (REMF-DESTRUCTION-UNSPECIFIED)   to clarify the
  761. permissible side effects of certain operations. When the sequence is a list,
  762. delete-duplicates is permitted to perform a setf on any part, car or cdr, of
  763. the top-level list structure of that list. When the sequence is an array,
  764. delete-duplicates is permitted to alter the dimensions of the given array and
  765. to slide some of its elements into new positions without permuting them in
  766. order to produce the resulting array.
  767. [change_end]
  768.  
  769. [Function]
  770.  
  771. substitute newitem olditem sequence &key :from-end :test :test-not
  772.            :start :end :count :key
  773. substitute-if newitem test sequence &key :from-end
  774.            :start :end :count :key
  775. substitute-if-not newitem test sequence &key :from-end
  776.            :start :end :count :key
  777.  
  778. The result is a sequence of the same kind as the argument sequence that has the
  779. same elements except that those in the subsequence delimited by :start and :end
  780. and satisfying the test (see above) have been replaced by newitem. This is a
  781. non-destructive operation; the result is a copy of the input sequence, save
  782. that some elements are changed.
  783.  
  784. The :count argument, if supplied, limits the number of elements altered; if
  785. more than :count elements satisfy the test, then of these elements only the
  786. leftmost are replaced, as many as specified by :count.
  787.  
  788. [change_begin]
  789. X3J13 voted in January 1989 (RANGE-OF-COUNT-KEYWORD)   to clarify that the
  790. :count argument must be either nil or an integer, and that supplying a negative
  791. integer produces the same behavior as supplying zero.
  792. [change_end]
  793.  
  794. A non-nil :from-end specification matters only when the :count argument is
  795. provided; in that case only the rightmost :count elements satisfying the test
  796. are replaced. For example:
  797.  
  798. (substitute 9 4 '(1 2 4 1 3 4 5)) => (1 2 9 1 3 9 5)
  799. (substitute 9 4 '(1 2 4 1 3 4 5) :count 1) => (1 2 9 1 3 4 5)
  800. (substitute 9 4 '(1 2 4 1 3 4 5) :count 1 :from-end t)
  801.    => (1 2 4 1 3 9 5)
  802. (substitute 9 3 '(1 2 4 1 3 4 5) :test #'>) => (9 9 4 9 3 4 5)
  803. (substitute-if 9 #'oddp '(1 2 4 1 3 4 5)) => (9 2 4 9 9 4 9)
  804. (substitute-if 9 #'evenp '(1 2 4 1 3 4 5) :count 1 :from-end t)
  805.    => (1 2 4 1 3 9 5)
  806.  
  807. The result of substitute may share with the argument sequence; a list result
  808. may share a tail with an input list, and the result may be eq to the input
  809. sequence if no elements need to be changed.
  810.  
  811. See also subst, which performs substitutions throughout a tree.
  812.  
  813. [change_begin]
  814. X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION)   to restrict
  815. user side effects; see section 7.9.
  816. [change_end]
  817.  
  818. [Function]
  819.  
  820. nsubstitute newitem olditem sequence &key :from-end :test :test-not
  821.                :start :end :count :key
  822. nsubstitute-if newitem test sequence &key :from-end
  823.                :start :end :count :key
  824. nsubstitute-if-not newitem test sequence &key :from-end
  825.                :start :end :count :key
  826.  
  827. This is the destructive counterpart to substitute. The result is a sequence of
  828. the same kind as the argument sequence that has the same elements except that
  829. those in the subsequence delimited by :start and :end and satisfying the test
  830. (see above) have been replaced by newitem. This is a destructive operation. The
  831. argument sequence may be destroyed and used to construct the result; however,
  832. the result may or may not be eq to sequence.
  833.  
  834. See also nsubst, which performs destructive substitutions throughout a tree.
  835.  
  836. [change_begin]
  837. X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION)   to restrict
  838. user side effects; see section 7.9.
  839.  
  840. X3J13 voted in March 1989 (REMF-DESTRUCTION-UNSPECIFIED)   to clarify the
  841. permissible side effects of certain operations. When the sequence is a list,
  842. nsubstitute or nsubstitute-if is required to perform a setf on any car of the
  843. top-level list structure of that list whose old contents must be replaced with
  844. newitem but is forbidden to perform a setf on any cdr of the list. When the
  845. sequence is an array, nsubstitute or nsubstitute-if is required to perform a
  846. setf on any element of the array whose old contents must be replaced with
  847. newitem. These functions, therefore, may successfully be used solely for
  848. effect, the caller discarding the returned value (though some programmers find
  849. this stylistically distasteful).
  850. [change_end]
  851.  
  852. -------------------------------------------------------------------------------
  853.  
  854. 14.4. Searching Sequences for Items
  855.  
  856. Each of these functions searches a sequence to locate one or more elements
  857. satisfying some test.
  858.  
  859. [Function]
  860.  
  861. find item sequence &key :from-end :test :test-not :start :end :key
  862. find-if predicate sequence &key :from-end :start :end :key
  863. find-if-not predicate sequence &key :from-end :start :end :key
  864.  
  865. If the sequence contains an element satisfying the test, then the leftmost such
  866. element is returned; otherwise nil is returned.
  867.  
  868. If :start and :end keyword arguments are given, only the specified subsequence
  869. of sequence is searched.
  870.  
  871. If a non-nil :from-end keyword argument is specified, then the result is the
  872. rightmost element satisfying the test.
  873.  
  874. [change_begin]
  875. X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION)   to restrict
  876. user side effects; see section 7.9.
  877. [change_end]
  878.  
  879. [Function]
  880.  
  881. position item sequence &key :from-end :test :test-not
  882.           :start :end :key
  883. position-if predicate sequence &key :from-end
  884.           :start :end :key
  885. position-if-not predicate sequence &key :from-end
  886.           :start :end :key
  887.  
  888. If the sequence contains an element satisfying the test, then the index within
  889. the sequence of the leftmost such element is returned as a non-negative
  890. integer; otherwise nil is returned.
  891.  
  892. If :start and :end keyword arguments are given, only the specified subsequence
  893. of sequence is searched. However, the index returned is relative to the entire
  894. sequence, not to the subsequence.
  895.  
  896. If a non-nil :from-end keyword argument is specified, then the result is the
  897. index of the rightmost element satisfying the test. (The index returned,
  898. however, is an index from the left-hand end, as usual.)
  899.  
  900. [change_begin]
  901. X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION)   to restrict
  902. user side effects; see section 7.9.
  903.  
  904. Here is a simple piece of code that uses several of the sequence functions,
  905. notably position-if and find-if, to process strings. Note one use of loop as
  906. well.
  907.  
  908. (defun debug-palindrome (s)
  909.   (flet ((match (x) (char-equal (first x) (third x))))
  910.     (let* ((pairs (loop for c across s
  911.                         for j from 0
  912.                         when (alpha-char-p c)
  913.                           collect (list c j)))
  914.            (quads (mapcar #'append pairs (reverse pairs)))
  915.            (diffpos (position-if (complement #'match) quads)))
  916.       (when diffpos
  917.         (let* ((diff (elt quads diffpos))
  918.                (same (find-if #'match quads
  919.                               :start (+ diffpos 1))))
  920.           (if same
  921.               (format nil
  922.                       "/~A/ (at ~D) is not the reverse of /~A/"
  923.                       (subseq s (second diff) (second same))
  924.                       (second diff)
  925.                       (subseq s (+ (fourth same) 1)
  926.                                 (+ (fourth diff) 1)))
  927.               "This palindrome is completely messed up!"))))))
  928.  
  929. Here is an example of its behavior.
  930.  
  931. (setq panama     ;A putative palindrome?
  932.       "A man, a plan, a canoe, pasta, heros, rajahs,
  933.        a coloratura, maps, waste, percale, macaroni, a gag,
  934.        a banana bag, a tan, a tag, a banana bag again
  935.        (or a camel), a crepe, pins, Spam, a rut, a Rolo,
  936.        cash, a jar, sore hats, a peon, a canal-Panama!")
  937.  
  938. (debug-palindrome panama)
  939.   => "/wast/ (at 73) is not the reverse of /, pins/"
  940.  
  941. (replace panama "snipe" :start1 73)     ;Repair it
  942.   => "A man, a plan, a canoe, pasta, heros, rajahs,
  943.        a coloratura, maps, snipe, percale, macaroni, a gag,
  944.        a banana bag, a tan, a tag, a banana bag again
  945.        (or a camel), a crepe, pins, Spam, a rut, a Rolo,
  946.        cash, a jar, sore hats, a peon, a canal-Panama!"
  947.  
  948. (debug-palindrome panama) => nil     ;Copacetic-a true palindrome
  949.  
  950. (debug-palindrome "Rubber baby buggy bumpers")
  951.   => "/Rubber / (at 0) is not the reverse of /umpers/"
  952.  
  953. (debug-palindrome "Common Lisp: The Language")
  954.   => "/Commo/ (at 0) is not the reverse of /guage/"
  955.  
  956. (debug-palindrome "Complete mismatches are hard to find")
  957.   =>
  958.   "/Complete mism/ (at 0) is not the reverse of /re hard to find/"
  959.  
  960. (debug-palindrome "Waltz, nymph, for quick jigs vex Bud")
  961.   => "This palindrome is completely messed up!"
  962.  
  963. (debug-palindrome "Doc, note: I dissent.  A fast never
  964.                    prevents a fatness.  I diet on cod.")
  965.   =>nil     ;Another winner
  966.  
  967. (debug-palindrome "Top step's pup's pet spot") => nil
  968.  
  969. [change_end]
  970.  
  971. [Function]
  972.  
  973. count item sequence &key :from-end :test :test-not :start :end :key
  974. count-if predicate sequence &key :from-end :start :end :key
  975. count-if-not predicate sequence &key :from-end :start :end :key
  976.  
  977. The result is always a non-negative integer, the number of elements in the
  978. specified subsequence of sequence satisfying the test.
  979.  
  980. The :from-end argument does not affect the result returned; it is accepted
  981. purely for compatibility with other sequence functions.
  982.  
  983. [change_begin]
  984. X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION)   to restrict
  985. user side effects; see section 7.9.
  986. [change_end]
  987.  
  988. [Function]
  989. mismatch sequence1 sequence2 &key :from-end :test :test-not :key :start1
  990. :start2 :end1 :end2
  991.  
  992. The specified subsequences of sequence1 and sequence2 are compared
  993. element-wise. If they are of equal length and match in every element, the
  994. result is nil. Otherwise, the result is a non-negative integer. This result is
  995. the index within sequence1 of the leftmost position at which the two
  996. subsequences fail to match; or, if one subsequence is shorter than and a
  997. matching prefix of the other, the result is the index relative to sequence1
  998. beyond the last position tested.
  999.  
  1000. If a non-nil :from-end keyword argument is given, then one plus the index of
  1001. the rightmost position in which the sequences differ is returned. In effect,
  1002. the (sub)sequences are aligned at their right-hand ends; then, the last
  1003. elements are compared, the penultimate elements, and so on. The index returned
  1004. is again an index relative to sequence1.
  1005.  
  1006. [change_begin]
  1007. X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION)   to restrict
  1008. user side effects; see section 7.9.
  1009. [change_end]
  1010.  
  1011. [Function]
  1012. search sequence1 sequence2 &key :from-end :test :test-not :key :start1 :start2
  1013. :end1 :end2
  1014.  
  1015. A search is conducted for a subsequence of sequence2 that element-wise matches
  1016. sequence1. If there is no such subsequence, the result is nil; if there is, the
  1017. result is the index into sequence2 of the leftmost element of the leftmost such
  1018. matching subsequence.
  1019.  
  1020. If a non-nil :from-end keyword argument is given, the index of the leftmost
  1021. element of the rightmost matching subsequence is returned.
  1022.  
  1023. The implementation may choose to search the sequence in any order; there is no
  1024. guarantee on the number of times the test is made. For example, search with a
  1025. non-nil :from-end argument might actually search a list from left to right
  1026. instead of from right to left (but in either case would return the rightmost
  1027. matching subsequence, of course). Therefore it is a good idea for a
  1028. user-supplied predicate to be free of side effects.
  1029.  
  1030. [change_begin]
  1031. X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION)   to restrict
  1032. user side effects; see section 7.9.
  1033. [change_end]
  1034.  
  1035. -------------------------------------------------------------------------------
  1036.  
  1037. 14.5. Sorting and Merging
  1038.  
  1039. These functions may destructively modify argument sequences in order to put a
  1040. sequence into sorted order or to merge two already sorted sequences.
  1041.  
  1042. [Function]
  1043. sort sequence predicate &key :key
  1044. stable-sort sequence predicate &key :key
  1045.  
  1046.   The sequence is destructively sorted according to an order determined by the
  1047. predicate. The predicate should take two arguments, and return non-nil if and
  1048. only if the first argument is strictly less than the second (in some
  1049. appropriate sense). If the first argument is greater than or equal to the
  1050. second (in the appropriate sense), then the predicate should return nil.
  1051.  
  1052. The sort function determines the relationship between two elements by giving
  1053. keys extracted from the elements to the predicate. The :key argument, when
  1054. applied to an element, should return the key for that element. The :key
  1055. argument defaults to the identity function, thereby making the element itself
  1056. be the key.
  1057.  
  1058. The :key function should not have any side effects. A useful example of a :key
  1059. function would be a component selector function for a defstruct structure, used
  1060. in sorting a sequence of structures.
  1061.  
  1062. (sort a p :key s)
  1063.    == (sort a #'(lambda (x y) (p (s x) (s y))))
  1064.  
  1065. While the above two expressions are equivalent, the first may be more efficient
  1066. in some implementations for certain types of arguments. For example, an
  1067. implementation may choose to apply s to each item just once, putting the
  1068. resulting keys into a separate table, and then sort the parallel tables, as
  1069. opposed to applying s to an item every time just before applying the predicate.
  1070.  
  1071. If the :key and predicate functions always return, then the sorting operation
  1072. will always terminate, producing a sequence containing the same elements as the
  1073. original sequence (that is, the result is a permutation of sequence). This is
  1074. guaranteed even if the predicate does not really consistently represent a total
  1075. order (in which case the elements will be scrambled in some unpredictable way,
  1076. but no element will be lost). If the :key function consistently returns
  1077. meaningful keys, and the predicate does reflect some total ordering criterion
  1078. on those keys, then the elements of the result sequence will be properly sorted
  1079. according to that ordering.
  1080.  
  1081. The sorting operation performed by sort is not guaranteed stable. Elements
  1082. considered equal by the predicate may or may not stay in their original order.
  1083. (The predicate is assumed to consider two elements x and y to be equal if
  1084. (funcall predicate x y) and (funcall predicate y x) are both false.) The
  1085. function stable-sort guarantees stability but may be slower than sort in some
  1086. situations.
  1087.  
  1088. The sorting operation may be destructive in all cases. In the case of an array
  1089. argument, this is accomplished by permuting the elements in place. In the case
  1090. of a list, the list is destructively reordered in the same manner as for
  1091. nreverse. Thus if the argument should not be destroyed, the user must sort a
  1092. copy of the argument.
  1093.  
  1094. Should execution of the :key function or the predicate cause an error, the
  1095. state of the list or array being sorted is undefined. However, if the error is
  1096. corrected, the sort will, of course, proceed correctly.
  1097.  
  1098. Note that since sorting requires many comparisons, and thus many calls to the
  1099. predicate, sorting will be much faster if the predicate is a compiled function
  1100. rather than interpreted.
  1101.  
  1102. An example:
  1103.  
  1104. (setq foovector (sort foovector #'string-lessp :key #'car))
  1105.  
  1106. If foovector contained these items before the sort
  1107.  
  1108. ("Tokens" "The Lion Sleeps Tonight")
  1109. ("Carpenters" "Close to You")
  1110. ("Rolling Stones" "Brown Sugar")
  1111. ("Beach Boys" "I Get Around")
  1112. ("Mozart" "Eine Kleine Nachtmusik" (K 525))
  1113. ("Beatles" "I Want to Hold Your Hand")
  1114.  
  1115. then after the sort foovector would contain
  1116.  
  1117. ("Beach Boys" "I Get Around")
  1118. ("Beatles" "I Want to Hold Your Hand")
  1119. ("Carpenters" "Close to You")
  1120. ("Mozart" "Eine Kleine Nachtmusik" (K 525))
  1121. ("Rolling Stones" "Brown Sugar")
  1122. ("Tokens" "The Lion Sleeps Tonight")
  1123.  
  1124. [change_begin]
  1125. X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION)   to restrict
  1126. user side effects; see section 7.9.
  1127. [change_end]
  1128.  
  1129. [Function]
  1130. merge result-type sequence1 sequence2 predicate &key :key
  1131.  
  1132. The sequences sequence1 and sequence2 are destructively merged according to an
  1133. order determined by the predicate. The result is a sequence of type
  1134. result-type, which must be a subtype of sequence, as for the function coerce.
  1135. The predicate should take two arguments and return non-nil if and only if the
  1136. first argument is strictly less than the second (in some appropriate sense). If
  1137. the first argument is greater than or equal to the second (in the appropriate
  1138. sense), then the predicate should return nil.
  1139.  
  1140. The merge function determines the relationship between two elements by giving
  1141. keys extracted from the elements to the predicate. The :key function, when
  1142. applied to an element, should return the key for that element; the :key
  1143. function defaults to the identity function, thereby making the element itself
  1144. be the key.
  1145.  
  1146. The :key function should not have any side effects. A useful example of a :key
  1147. function would be a component selector function for a defstruct structure, used
  1148. to merge a sequence of structures.
  1149.  
  1150. If the :key and predicate functions always return, then the merging operation
  1151. will always terminate. The result of merging two sequences x and y is a new
  1152. sequence z, such that the length of z is the sum of the lengths of x and y, and
  1153. z contains all the elements of x and y. If x1 and x2 are two elements of x, and
  1154. x1 precedes x2 in x, then x1 precedes x2 in z, and similarly for elements of y.
  1155. In short, z is an interleaving of x and y.
  1156.  
  1157. Moreover, if x and y were correctly sorted according to the predicate, then z
  1158. will also be correctly sorted, as shown in this example.
  1159.  
  1160. (merge 'list '(1 3 4 6 7) '(2 5 8) #'<) => (1 2 3 4 5 6 7 8)
  1161.  
  1162. If x or y is not so sorted then z will not be sorted, but will nevertheless be
  1163. an interleaving of x and y.
  1164.  
  1165. The merging operation is guaranteed stable; if two or more elements are
  1166. considered equal by the predicate, then the elements from sequence1 will
  1167. precede those from sequence2 in the result. (The predicate is assumed to
  1168. consider two elements x and y to be equal if (funcall predicate x y) and
  1169. (funcall predicate y x) are both false.) For example:
  1170.  
  1171. (merge 'string "BOY" "nosy" #'char-lessp) => "BnOosYy"
  1172.  
  1173. The result can not be "BnoOsYy", "BnOosyY", or "BnoOsyY". The function
  1174. char-lessp ignores case, and so considers the characters Y and y to be equal,
  1175. for example; the stability property then guarantees that the character from the
  1176. first argument (Y) must precede the one from the second argument (y).
  1177.  
  1178. [change_begin]
  1179. X3J13 voted in June 1989 (SEQUENCE-TYPE-LENGTH)   to specify that merge should
  1180. signal an error if the sequence type specifies the number of elements and the
  1181. sum of the lengths of the two sequence arguments is different.
  1182.  
  1183. X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION)   to restrict
  1184. user side effects; see section 7.9.
  1185. [change_end]
  1186.  
  1187. -------------------------------------------------------------------------------
  1188.  
  1189.  
  1190.